package com.zss.leetcode;


/**
 * 回文链表
 * @author fuguozhang
 * @create 2022/5/17
 */
public class PalindromeList {

    private ListNode frontPointer;

    public static void main(String[] args) {
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(2);
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        boolean res = huiwenList(node1);
        System.out.println(res);

        res = new PalindromeList().palindromeList2(node1);
        System.out.println(res);

        res = palindromeList3(node1);
        System.out.println(res);
    }

    /**
     * 复制数组，左右指针迭代
     * @param l
     * @return
     */
    public static boolean huiwenList(ListNode l){
        int[] vals = new int[5];
        int i = 0;
        while (l != null){
            vals[i] = l.val;
            i++;
            l = l.next;
        }
        int left = 0,right = vals.length - 1;
        while (left < right){
            if(vals[left] == vals[right]){
                left++;
                right--;
            }else {
                return false;
            }
        }
        return true;
    }

    /**
     * 递归方法
     * @param head
     * @return
     */
    public boolean palindromeList2(ListNode head){
        frontPointer = head;
        return recursiverlyCheck(head);
    }

    public boolean recursiverlyCheck(ListNode currentNode){
        if(currentNode != null){
            if(!recursiverlyCheck(currentNode.next)){
                return false;
            }
            if(currentNode.val != frontPointer.val){
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    /**
     * 快慢指针
     * @param head
     * @return
     */
    public static boolean palindromeList3(ListNode head){
        if(head == null){
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode sub = reverseList(slow.next);

        ListNode p1 = head;
        ListNode p2 = sub;
        boolean result = true;
        while (result && p2 != null){
            if(p1.val != p2.val){
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        slow.next = reverseList(sub);
        return result;
    }

    /**
     * 链表反转，迭代
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static class ListNode{
        private int val;
        private ListNode next;
        public ListNode(int val){
            this.val = val;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }
}
